from typing import List
"""
面试题：找出数组中重复的数字
此题的前提是无法确定重复的数字的个数，即找到任意一个重复的数字
分析思路：

for i in data:
   m = a[i]
   if m == i:
      继续扫描下一个数字
   else
      if m == a[m]:
         m即是 重复的数字
      else:
         则将交换 第i个数字和第m个数字
         swap(a[i], a[m])
"""


class Solution():
    def duplicate(self, numbers: List, dup_number: List):
        if len(numbers) <= 0:
            return False
        for i in range(len(numbers)):
            if i != numbers[i]:
                m = numbers[i]
                if m == numbers[m]:
                    dup_number.append(m)
                    return True
                else:
                    numbers[i] = numbers[m]
                    numbers[m] = m


def test_duplicate():
    test_dup = Solution()
    test_numbers = [2,3,1,0,2,5,3]
    dup_number = []
    test_dup.duplicate(test_numbers, dup_number)
    print(dup_number)


"""
改进版：在不修改数组的情况下找出数组中重复的数字
分析思路：
利用二分查找的思路

"""

class Solution2:
    def count_range(self, numbers, start, end):
        if len(numbers) <= 0:
            return 0
        count = 0
        for i in range(len(numbers)):
            if numbers[i] >= start and numbers[i] <= end:
                count += 1
        return count

    def duplicate(self, numbers: List):
        if len(numbers) <= 0:
            return False
        start = 1
        end = len(numbers) - 1
        while end >= start:
            middle = start + ((end - start)//2)
            count = self.count_range(numbers, start, end)
            if end == start:
                if count > 1:
                    return numbers[start]
                else:
                    break
            if count > middle-start+1:
                end = middle
            else:
                start = middle + 1
        return -1

def test_duplicate2():
    test_dup = Solution2()
    test_numbers = [2,3,1,0,2,5,3]
    print(test_dup.duplicate(test_numbers))


if __name__ == '__main__':
    test_duplicate()

    test_duplicate2()
